/*************************************************************************
 * File Name:    Sudoku_Solver.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: 2013-11-8 16:37:04
 * 
 * Description:  
 |------------------------------------------------------------------------
 | Sudoku Solver Total Accepted: 1108 Total Submissions: 5621 My Submissions
 | Write a program to solve a Sudoku puzzle by filling the empty cells.
 |
 | Empty cells are indicated by the character '.'.
 |
 | You may assume that there will be only one unique solution.
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>

using namespace std;

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board)
    {
        int row, col;
        
        for (int i = 0; i < cell_size; ++i) {
            for (int j = 0; j < cell_size; ++j) {
                if (board[i][j] != '.') continue;
                
                search(i, j, board);
                return;
            }
        }
    }
    
private:
    bool search(int i, int j, vector<vector<char> > &board)
    {
        vector<char> rem_num = get_num_list(i, j, board);
        
        int r, c;
        for (r = 0; r < cell_size; ++r) {
            for (c = 0; c < cell_size; ++c) {
                if (board[r][c] == '.' && !(r == i && c == j)) break;
            }
            if (c < cell_size) break;
        }
        if (r >= cell_size) {
            if (rem_num.size() > 0) {
                board[i][j] = rem_num[0];
                return true;
            }
            return false;
        }
        
        for (size_t k = 0; k < rem_num.size(); ++k) {
            board[i][j] = rem_num[k];
            if (search(r, c, board)) return true;
        }
        board[i][j] = '.';
        return false;
    }
    
    vector<char> get_num_list(int i, int j, const vector<vector<char> > &board)
    {
        vector<char> num_list;
        int row, col, id;
        bool find;
        
        for (int k = 1; k <= cell_size; ++k) {
            find = false;
            
            id = i / cell_width * cell_width + j / cell_width;
            for (int s = 0; s < cell_size; ++s) {
                row = id / cell_width * cell_width + s / cell_width;
                col = id % cell_width * cell_width + s % cell_width;
                if (board[row][col] == k + '0') find = true;
                if (board[s][j] == k + '0') find = true;
                if (board[i][s] == k + '0') find = true;
                if (find) break;
            }
            if (find) continue;
            num_list.push_back(k + '0');
        }
        return num_list;
    }
    
private:
    const int cell_width = 3;
    const int cell_size = cell_width * cell_width;
};

